#ifndef _DFA_BASE_STR
#define _DFA_BASE_STR

#include "Set.h"
#include <map>
#include <vector>
#include <string>

namespace dfa_base_str {			// dfa base structure
	class Out_of_mem {};
	typedef mylib::Set<int> Pos_set;
	class Lex_oper {
	public:
		class Invalid_oper {};				// invalid operation
		class Invalid_input {};
		virtual Lex_oper &cal()=0;			// calculate the first last value
		virtual const Pos_set &first()=0;		// return the first value
		virtual const Pos_set &last()=0;		// return the last value
		virtual bool nul()= 0;				// return the nullabel value
		~Lex_oper() {}
	};
	class Start : virtual public Lex_oper {
	public :
		Start(Lex_oper &s) : reg(s) { }
		Start(Start &s) : reg(s.reg) { }
		Start &cal() { return *this; }
		const Pos_set &first() { return reg.first(); }
		const Pos_set &last() { return reg.last(); }
		bool nul() { return reg.nul(); }
		Lex_oper &child() { return reg; }
	private :
		Lex_oper &reg;
	};
	class Start_line : virtual public Lex_oper {		// ^				new
	public:
		Start_line() {}
		Start_line(Start_line &s) { }
		Start_line &cal() { throw Lex_oper::Invalid_oper();}
		const Pos_set &first() {throw Lex_oper::Invalid_oper();}
		const Pos_set &last() {throw Lex_oper::Invalid_oper();}
		bool nul() {return false;}
	};
	class Kleen : virtual public Lex_oper {
	public:
		Kleen(Lex_oper &c) : reg(c){calculated=false;}
		Kleen(Kleen &k) : reg(k.reg) { calculated=k.calculated;first_val=k.first_val;last_val=k.last_val; }

		Kleen &cal();
		const Pos_set &first() { if( !calculated ) cal(); return first_val; }
		const Pos_set &last() { if( !calculated ) cal(); return last_val; }
		bool nul() { return true; }
		Lex_oper &child() { return reg; }
	private :
		Pos_set first_val;
		Pos_set last_val;
		Lex_oper &reg;
		bool calculated;			// to label calculated
	};
	class One_more : virtual public Lex_oper {
	public :
		One_more(Lex_oper &c) : reg(c) { calculated = false; }
		One_more(One_more &c) : reg(c.reg) {
			nullabel=c.nullabel; calculated=c.calculated; first_val=c.first_val;last_val=c.last_val; 
		}

		One_more &cal();
		const Pos_set &first(){if(!calculated) cal(); return first_val; }
		const Pos_set &last() {if(!calculated) cal(); return last_val; }
		bool nul() { if(!calculated) cal(); return nullabel; }
		Lex_oper &child() { return reg; }
	private :
		Lex_oper &reg;
		Pos_set first_val;
		Pos_set last_val;
		bool nullabel;
		bool calculated;			// to label calculated
	};
	class Zero_one : virtual public Lex_oper {
	public :
		Zero_one(Lex_oper &c) : reg(c) { calculated=false; }
		Zero_one(Zero_one &c) : reg(c.reg) {calculated=c.calculated; first_val=c.first_val; last_val=c.last_val; }

		Zero_one &cal();
		const Pos_set &first(){if(!calculated) cal(); return first_val; }
		const Pos_set &last() {if(!calculated) cal(); return last_val; }
		bool nul() { return true; }
		Lex_oper &child() { return reg; }
	private :
		Lex_oper &reg;
		Pos_set first_val;
		Pos_set last_val;
		bool calculated;
	};
	class Concate : virtual public Lex_oper {
	public:
		Concate(Lex_oper &lr, Lex_oper &rr) : left(lr), right(rr) { calculated=false;}
		Concate(Concate &c) : left(c.left), right(c.right) { 
			nullabel=c.nullabel; calculated=c.calculated; first_val=c.first_val; last_val=c.last_val; 
		}
		Concate &cal();
		const Pos_set &first(){if(!calculated) cal(); return first_val; }
		const Pos_set &last() {if(!calculated) cal(); return last_val; }
		bool nul(){ if(!calculated) cal(); return nullabel; }
		Lex_oper &l_child()const { return left; }
		Lex_oper &r_child()const { return right; }
	private:
		Lex_oper &left;
		Lex_oper &right;
		Pos_set first_val;
		Pos_set last_val;
		bool nullabel;
		bool calculated;
	};
	class Union : virtual public Lex_oper {
	public :
		Union(Lex_oper &lr, Lex_oper &rr) : left(lr), right(rr) { calculated=false; }
		Union(Union &u) : left(u.left), right(u.right){
			nullabel=u.nullabel; calculated=u.calculated; first_val=u.first_val; last_val=u.last_val;
		}

		Union &cal();
		const Pos_set &first(){if(!calculated) cal(); return first_val; }
		const Pos_set &last() {if(!calculated) cal(); return last_val; }
		bool nul() { if(!calculated) cal(); return nullabel; }
		Lex_oper &l_child()const { return left; }
		Lex_oper &r_child()const { return right; }
	private :
		Lex_oper &left;
		Lex_oper &right;
		Pos_set first_val;
		Pos_set last_val;
		bool nullabel;
		bool calculated;
	};
	class Suffix : virtual public Lex_oper {
	public :
		Suffix(Lex_oper &lr, Lex_oper &rr) : left(lr), right(rr) { calculated=false;}
		Suffix(Suffix &s) : left(s.left), right(s.right) { 
			calculated=s.calculated; nullabel=s.nullabel; first_val=s.first_val; last_val=s.last_val;
		}

		Suffix &cal();
		const Pos_set &first(){if(!calculated) cal(); return first_val; }
		const Pos_set &last() {if(!calculated) cal(); return last_val; }
		bool nul(){ if(!calculated) cal(); return nullabel; }
		Lex_oper &l_child()const { return left; }
		Lex_oper &r_child()const { return right; }
	private :
		Lex_oper &left;
		Lex_oper &right;
		Pos_set first_val;
		Pos_set last_val;
		bool nullabel;
		bool calculated;
	};
	class Reg_base : virtual public Lex_oper {
	public :
		Reg_base(const mylib::Set<char> &eles, int p=0) : elets(eles){
			if(p < 0) throw Invalid_input(); else pos=p;
			calculated=false;
		}
		Reg_base(Reg_base &base) : elets(base.elets) {pos=base.pos;fir_last=base.fir_last;calculated=base.calculated;}

		Reg_base &cal(){if(!calculated) fir_last += pos; return *this; }
		Reg_base &set_pos(const int p) { 
			if( pos < 0 ) throw Invalid_input(); 
			else if(calculated) {fir_last.clear(); calculated=false; }
			pos=p;	return *this;
		}
		const Pos_set &first(){if(!calculated) cal(); return fir_last; }
		const Pos_set &last() {if(!calculated) cal(); return fir_last; }
		const mylib::Set<char> &element() const { return elets; }
		int position() { return pos; }
		bool nul() { return false; }
	private :
		int pos;
		const mylib::Set<char> elets;
		Pos_set fir_last;
		bool calculated;
	};
	class Eplilon : virtual public Lex_oper {
	public:
		Eplilon() {}
		Eplilon(const Eplilon &e) {}

		Eplilon &cal(){throw Lex_oper::Invalid_oper();}		// calculate at constructor
		const Pos_set &first(){ throw Invalid_oper(); }
		const Pos_set &last() { throw Invalid_oper(); }
		bool nul() { return true; }
	};
	class End_mark : virtual public Lex_oper {
	public:
		End_mark(int p=0) {
			if(p < 0) throw Invalid_input(); else pos=p;
			calculated=false;
		}
		End_mark(End_mark &base) {pos=base.pos;fir_last=base.fir_last;calculated=base.calculated;}

		End_mark &cal(){if(!calculated) fir_last += pos; return *this; }
		End_mark &set_pos(const int p) { 
			if( pos < 0 ) throw Invalid_input(); 
			else if(calculated) {fir_last.clear(); calculated=false; }
			pos=p;	return *this;
		}
		const Pos_set &first(){if(!calculated) cal(); return fir_last; }
		const Pos_set &last() {if(!calculated) cal(); return fir_last; }
		int position() { return pos; }
		bool nul() { return false; }
	private :
		int pos;
		Pos_set fir_last;
		bool calculated;
	};
	Lex_oper *copyn_reg_tree(const Lex_oper &tree, size_t n);
	bool print_reg_tree(std::ostream &out, Lex_oper &reg_tree);
	bool del_reg_tree(Lex_oper &reg_tree);
	struct Reg_tree;
	struct Dfa_tree {
		Reg_tree *start;
		Reg_tree *entity;
		Reg_tree *suffix;
		bool start_line;
	};
	struct Reg_tree {
		Lex_oper *tree;
		mylib::Set<char> char_set;
		~Reg_tree() {if(tree) del_reg_tree(*tree); }
	};
	struct Pos_reg {
		mylib::Set<int> pos_set;
		dfa_base_str::Lex_oper *oper;
		Pos_reg(){oper=0;}
		friend std::ostream &operator<<(std::ostream &out, const Pos_reg &p) { out << p.pos_set; return out; }
	};
	typedef std::vector<Pos_reg> Fol_val;
}
#endif
